# k个一组反转链表： https://leetcode-cn.com/problems/reverse-nodes-in-k-group/


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

        
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        """
            首先对于整个反转的情况， 还是要设立 首元结点，统一逻辑

            1. 先将k长度链表片段反转
            2. 再拼接到原来串中
            
            假设有（加了首元结点的串） dumpy -> 1 -> 2 -> 3 -> 4 -> 5，    k = 2
            变量名字可能有点乱
            param:      h: 开始指向 交换区间的前一个节点，初始为 dumpy
            param:      p: 负责遍历每一个节点，初始为 head
            param:      cur: 代表当前节点，因为 p节点要 向后移动， 初始为 p
            param:      pre: 链表做反转时用到的， cur.next = pre, 初始为 None
            param:      temp: 代表的是链表片段的第一个元素

            以第一次遍历举例
            h = dumpy
            pre = None
            cur = p = head  为 1

            temp = h.next
            # 反转链表片段
            for j in range(k):
                cur = p
                p = p.next
                cur.next = pre
                pre = cur

            # 拼接回去
            temp.next = p
            h.next = cur

            h = temp    

        """
        dumpy = ListNode(0, head)

        # 1. 先求链表长度
        n = 0
        cur = head
        while cur:
            cur = cur.next
            n += 1
        
        h = dumpy
        pre = None
        cur = p = head
        # 2. 注意1： 需要反转次数，就是取步长k, 这里起点是 k - 1, 最后不满足k是不会进行循环的
        for i in range(k - 1, n, k):
            # 交换 k 长链表
            temp = h.next
            for j in range(k):
                cur = p
                p = p.next
                cur.next = pre
                pre = cur
             
            temp.next = p
            h.next = cur

            h = temp    
    
        return dumpy.next


